package com.huaxia.day11;

import java.util.Arrays;

public class BubbleSort {
    public static void main(String[] args) {
        int[] arr = {6, 3, 8, 2, 9, 1};

        System.out.println("排序前数组为：");
        for (int num : arr) {
            System.out.print(num + " ");
        }
        sort(arr);
        System.out.println();
        System.out.println("排序后的数组为：");
        for (int num : arr) {
            System.out.print(num + " ");
        }


    }

    public static void arraysSort(int arr[]) {
        // TODO Arrays 工具排序
        Arrays.sort(arr);
        for (int i : arr) {
            System.out.print(i);
            System.out.print(",");
        }
    }


    public static void sort(int arr[]) {
        if (arr == null) {
            return;
        }
        for (int i = 0; i < arr.length - 1; i++) {//外层循环控制排序趟数
            for (int j = 0; j < arr.length - 1 - i; j++) {//内层循环控制每一趟排序多少次
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
            print(i + 1, arr);
        }
    }

    public static void print(int count, int[] data) {
        System.out.println();
        System.out.println(String.format("第%s趟排序", count));
        for (int num : data) {
            System.out.print(num + " ");
        }
        //System.out.println();
    }

    /**
     * 大O表示法就是将算法的所有步骤转换为代数项，然后排除不会对问题的整体复杂度产生较大影响的较低阶常数和系数。
     * O(1)—常量时间：给定一个大小为n的输入，概算法只需要一步就可以完成任务。
     * O(log n)— 对数时间：给定大小为n的输入，该算法每执行一步，它完成任务所需要的步骤数目会以一定的因子减少。
     * O(n)— 线性时间：给定大小为n的输入，该算法完成任务所需要的步骤直接和n相关（1对1的关系）。
     * O(n²)—二次方时间：给定大小为n的输入，完成任务所需要的步骤是n的平方。
     * O(C^n)— 指数时间：给定大小为n的输入，完成任务所需要的步骤是一个常数的n次方（非常大的数字）。

     若文件的初始状态是正序的，一趟扫描即可完成排序。所需的关键字比较次数C和记录移动次数M均达到最小值
     C=n-1; M=0.
     所以，冒泡排序最好的时间复杂度为O(n)。

     若初始文件是反序的，需要进行n-1趟排序。每趟排序要进行n-i次关键字的比较(1≤i≤n-1)，且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下，比较和移动次数均达到最大值：
     C=n*(n-1)/2=O(n^2); M=3n*(n-1)/2=O(n^2).
     冒泡排序的最坏时间复杂度为O(n^2).

     综上，因此冒泡排序总的平均时间复杂度为O(n^2).
     */
}
